{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 冒泡排序\n",
    "\n",
    "![application](http://img.foshanplus.com/algo/bubble_sort.gif)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bubble_sort(arr):\n",
    "    \"\"\"冒泡排序\"\"\"\n",
    "    number = len(arr)   # 数组的长度\n",
    "    has_changed = True  # 一趟遍历中是否发生过交换\n",
    "    x = 0\n",
    "    while has_changed:\n",
    "        has_changed = False   # 每次循环复位\n",
    "        for i in range(1, number-x):  # 每次循环减少一次，因为后面的数列已经是有序\n",
    "            if arr[i-1] > arr[i]:\n",
    "                arr[i-1], arr[i] = arr[i], arr[i-1] # 交换位置\n",
    "                has_changed = True\n",
    "        x += 1\n",
    "    return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7]\n"
     ]
    }
   ],
   "source": [
    "print(bubble_sort([4,5,7,6,3,2,1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 三角形大比拼"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "metadata": {},
   "outputs": [],
   "source": [
    " def largest_perimeter(arr):\n",
    "        \"\"\"\n",
    "        寻找最大周长的三角形\n",
    "        输入：一组边长数据:list\n",
    "        \"\"\"\n",
    "        arr = bubble_sort(arr)  # 用冒泡排序\n",
    "        res = 0\n",
    "        for i in range(len(arr)-1, 1, -1):  # 从大到小遍历, \n",
    "            if arr[i-2] + arr[i-1] > arr[i]: # 满足三角形条件\n",
    "                res = arr[i-2] + arr[i-1] + arr[i]\n",
    "                print('三角形的周长是{}, 三条边长度分别是{},{},{}'.format(\n",
    "                    res, arr[i], arr[i-1], arr[i-2]))\n",
    "                break   # 已经找到结果不需要继续，跳出循环\n",
    "        if res == 0:\n",
    "            print(\"没有找能够组合三角形的棍子\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "三角形的周长是11, 三条边分别长度为5,4,2\n",
      "没有找能够组合三角形的棍子\n",
      "三角形的周长是2372, 三条边分别长度为845,780,747\n"
     ]
    }
   ],
   "source": [
    "largest_perimeter([4,14,9,5,2])\n",
    "largest_perimeter([20,10,1,2,7])\n",
    "largest_perimeter([233,120,747,75,67,336,221,845,780,403])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 187,
   "metadata": {},
   "outputs": [],
   "source": [
    " def largest_perimeter_2(arr):\n",
    "        \"\"\"寻找最大周长的三角形，优化排序过程，一边排序一边寻找答案\"\"\"\n",
    "        if len(arr) < 3:\n",
    "            print(\"数据不够，至少有三个元素！\")\n",
    "        else:\n",
    "            max_index = len(arr) -1  # 数组最大下标\n",
    "            res = 0                  # 三角形周长\n",
    "            # 冒泡排序\n",
    "            for i in range(max_index):\n",
    "                for j in range(max_index-i):\n",
    "                    if arr[j] > arr[j+1]:   # 相邻元素比较，交换位置\n",
    "                        arr[j], arr[j+1] = arr[j+1], arr[j]\n",
    "                if i >= 2: # 从大到小，找到三个有序元素后，开始尝试组合三角形\n",
    "                    if arr[max_index - i] + arr[max_index-i + 1] > arr[max_index - i + 2]:\n",
    "                        res = arr[max_index - i] + arr[max_index-i + 1] + arr[max_index - i + 2]\n",
    "                        print('三角形的周长是{}, 三条边长度分别是{},{},{}'.format(\n",
    "                            res, arr[max_index - i], arr[max_index-i + 1], arr[max_index - i + 2]))\n",
    "                        return\n",
    "            if arr[0] + arr[1] > arr[2] and res == 0: # 上面少比较了最后3个元素\n",
    "                res = arr[0] + arr[1] + arr[2]\n",
    "                print('三角形的周长是{}, 三条边长度分别是{},{},{}'.format(\n",
    "                            res, arr[0], arr[1], arr[2]))\n",
    "                return\n",
    "            if res == 0:\n",
    "                print(\"没有找能够组合三角形的棍子\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 189,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "三角形的周长是11, 三条边长度分别是2,4,5\n",
      "没有找能够组合三角形的棍子\n",
      "三角形的周长是2372, 三条边长度分别是747,780,845\n"
     ]
    }
   ],
   "source": [
    "largest_perimeter_2([4,14,9,5,2])\n",
    "largest_perimeter_2([20,10,1,2,7])\n",
    "largest_perimeter_2([233,120,747,75,67,336,221,845,780,403])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###  选择排序\n",
    "\n",
    "![application](http://img.foshanplus.com/algo/selection_sort.gif)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def selection_sort(arr):\n",
    "    \"\"\"选择排序\"\"\"\n",
    "    for i in range(len(arr)):\n",
    "        min_index = i   # 初始化下标，以无序序列的第一个元素为开始\n",
    "        for j in range(i + 1, len(arr)):\n",
    "            if arr[j] < arr[min_index]: # 从待排序序列中找最小值\n",
    "                min_index = j  # 把最小值下标记录下来\n",
    "        arr[min_index], arr[i] = arr[i], arr[min_index] # 当前位置元素交换位置\n",
    "    return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7]\n"
     ]
    }
   ],
   "source": [
    "print(selection_sort([4,5,7,6,3,2,1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 稳定性比较"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "冒泡排序 ['chenqiang', 'lili', 'liming', 'zhaosi', 'zhangxiaofei']\n",
      "选择排序 ['chenqiang', 'lili', 'liming', 'zhaosi', 'zhangxiaofei']\n",
      "冒泡排序 ['chenqiang', 'lili', 'liming', 'zhaosi', 'zhangxiaofei']\n",
      "选择排序 ['chenqiang', 'lili', 'liming', 'zhangxiaofei', 'zhaosi']\n"
     ]
    }
   ],
   "source": [
    "def name_bubble_sort(arr):\n",
    "    \"\"\"冒泡排序\"\"\"\n",
    "    number = len(arr)   # 数组的长度\n",
    "    has_changed = True  # 一趟遍历中是否发生过交换\n",
    "    x = 0\n",
    "    while has_changed:\n",
    "        has_changed = False   # 每次循环复位\n",
    "        for i in range(1, number-x):  # 每次循环减少一次，因为后面的数列已经是有序\n",
    "            if arr[i-1][0] > arr[i][0]: # 只是比较首字母\n",
    "                arr[i-1], arr[i] = arr[i], arr[i-1] # 交换位置\n",
    "                has_changed = True\n",
    "        x += 1\n",
    "    return arr\n",
    "def name_selection_sort(arr):\n",
    "    \"\"\"选择排序\"\"\"\n",
    "    for i in range(len(arr)):\n",
    "        min_index = i   # 初始化下标，以无序序列的第一个元素为开始\n",
    "        for j in range(i + 1, len(arr)):\n",
    "            if arr[j][0] < arr[min_index][0]: # 从待排序序列中找最小值，只比较首字母\n",
    "                min_index = j  # 把最小值下标记录下来\n",
    "        arr[min_index], arr[i] = arr[i], arr[min_index] # 当前位置元素交换位置\n",
    "#         print(arr)\n",
    "    return arr\n",
    "data = ['zhaosi','lili','chenqiang','liming','zhangxiaofei']\n",
    "print('冒泡排序',name_bubble_sort(data))\n",
    "data = ['zhaosi','lili','chenqiang','liming','zhangxiaofei']\n",
    "print('选择排序',name_selection_sort(data))\n",
    "\n",
    "data2 = ['chenqiang','zhaosi','lili','zhangxiaofei','liming']\n",
    "print('冒泡排序', name_bubble_sort(data2))\n",
    "data2 = ['chenqiang','zhaosi','lili','zhangxiaofei','liming']\n",
    "print('选择排序',name_selection_sort(data2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 插入排序\n",
    "\n",
    "![application](http://img.foshanplus.com/algo/insertion_sort.gif)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertion_sort(arr):\n",
    "    \"\"\"直接插入排序\"\"\"\n",
    "    for i in range(len(arr)): \n",
    "        key = arr[i]  # 暂存当前元素值\n",
    "        position = i       # 记录位移位置\n",
    "        while position > 0 and key < arr[position - 1] :\n",
    "            arr[position] = arr[position - 1]\n",
    "            position -= 1  # 位移多一次，下标值减一\n",
    "        arr[position] = key # 把之前元素插入到这个位置\n",
    "    return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7]\n"
     ]
    }
   ],
   "source": [
    "print(insertion_sort([4,5,7,6,3,2,1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_sertion_sort(arr):\n",
    "    \"\"\"折半插入排序\"\"\"\n",
    "    for i in range(len(arr)):\n",
    "        key = arr[i]         # 暂存当前元素值\n",
    "        position_low = 0     # 有序序列第一位元素下标\n",
    "        position_hight = i-1 # 有序序列末位元素下标\n",
    "        while position_low <= position_hight:\n",
    "            mid = (position_low + position_hight) // 2  # 中间元素下标\n",
    "            if key > arr[mid]:\n",
    "                position_low = mid + 1   # 看中间位置右半部分\n",
    "            else:\n",
    "                position_hight = mid - 1  # 看中间位置左半部分\n",
    "        # 找到插入位置后，下标值为position_low(mid值也相同)\n",
    "        for j in range(i, position_low, -1):\n",
    "            arr[j] = arr[j - 1]   # 向右位移，腾出空间插入新元素\n",
    "        arr[position_low] = key   # 插入新元素\n",
    "    return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7]\n"
     ]
    }
   ],
   "source": [
    "print(binary_sertion_sort([4,5,7,6,3,2,1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 归并排序\n",
    "\n",
    "![application](http://img.foshanplus.com/algo/merge_sort.gif)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge_sort(arr):\n",
    "    \"\"\"归并排序\"\"\"\n",
    "    if len(arr) <= 1:    # 不多于一个元素，最小的子序列，不用继续拆分\n",
    "        return arr\n",
    "    mid = len(arr) // 2  # 找到序列中间位置的下标  \n",
    "    # 中间分开左右两个子序列，子序列递归调用merge_sort()函数进行归并排序\n",
    "    left, right = merge_sort(arr[:mid]), merge_sort(arr[mid:])\n",
    "    # 返回的结果是有序的子序列，然后把子序列通过merge()函数合并子序列\n",
    "    return merge(left, right)\n",
    "\n",
    "def merge(left, right):\n",
    "    \"\"\"左右子序列合并\"\"\"\n",
    "    merged = left + right  # 创建一个和左右子序列相同大小的列表\n",
    "    left_positon, right_positon = 0, 0\n",
    "    while left_positon < len(left) and right_positon < len(right):\n",
    "        # 对左右子序列每个元素进行比较排序，放到新的有序序列里面\n",
    "        if left[left_positon] <= right[right_positon]:\n",
    "            merged[left_positon+right_positon]=left[left_positon]\n",
    "            left_positon += 1\n",
    "        else:\n",
    "            merged[left_positon + right_positon] = right[right_positon]\n",
    "            right_positon += 1\n",
    "    # 如果某一边子序列已经排序结束，那么把另外一边的子序列直接加到新的序列后面\n",
    "    for left_positon in range(left_positon, len(left)):\n",
    "        merged[left_positon + right_positon] = left[left_positon]\n",
    "    for right_positon in range(right_positon, len(right)):\n",
    "        merged[left_positon + right_positon] = right[right_positon]\n",
    "    return merged"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7]\n"
     ]
    }
   ],
   "source": [
    "print(merge_sort([4,5,7,6,3,2,1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 谁是大富翁"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge_sort_2(arr):\n",
    "    \"\"\"归并排序\"\"\"\n",
    "    if len(arr) <= 1:    # 不多于一个元素，最小的子序列，不用继续拆分\n",
    "        return arr\n",
    "    mid = len(arr) // 2  # 找到序列中间位置的下标  \n",
    "    # 中间分开左右两个子序列，子序列递归调用merge_sort()函数进行归并排序\n",
    "    left, right = merge_sort_2(arr[:mid]), merge_sort_2(arr[mid:])\n",
    "    # 返回的结果是有序的子序列，然后把子序列通过merge()函数合并子序列\n",
    "    return merge_2(left, right)\n",
    "\n",
    "def merge_2(left, right):\n",
    "    \"\"\"左右子序列合并\"\"\"\n",
    "    merged = left + right  # 创建一个和左右子序列相同大小的列表\n",
    "    left_positon, right_positon = 0, 0\n",
    "    \n",
    "    while left_positon < len(left) and right_positon < len(right):\n",
    "        # 判断元素的位置\n",
    "        if compare(left[left_positon],right[right_positon]): # 和上面算法区别就是这里，改变了规则\n",
    "            merged[left_positon+right_positon]=left[left_positon]\n",
    "            left_positon += 1\n",
    "        else:\n",
    "            merged[left_positon + right_positon] = right[right_positon]\n",
    "            right_positon += 1\n",
    "    # 如果某一边子序列已经排序结束，那么把另外一边的子序列直接加到新的序列后面\n",
    "    for left_positon in range(left_positon, len(left)):\n",
    "        merged[left_positon + right_positon] = left[left_positon]\n",
    "    for right_positon in range(right_positon, len(right)):\n",
    "        merged[left_positon + right_positon] = right[right_positon]\n",
    "    return merged\n",
    "\n",
    "def compare(a,b):\n",
    "    \"\"\"\n",
    "    比较两个元素的最高位数字大小，最高位相同则比较次高位，\n",
    "    若一边位数不足，可以继续使用最后一位的数字来比较\n",
    "    返回结果：\n",
    "    False代表a<=b,\n",
    "    True代表a>b\n",
    "    \"\"\"\n",
    "    if len(b) > len(a): # 找到比较长的字符串\n",
    "        max_index = len(b) \n",
    "    else:\n",
    "        max_index = len(a)\n",
    "    \n",
    "    # 字符串默认是可以通过下标来表示单个字符\n",
    "    for position in range(max_index):\n",
    "        if position >= len(a):  # -1表示倒数第一的元素\n",
    "            position_a = -1\n",
    "        else:\n",
    "            position_a = position\n",
    "        if position >= len(b):\n",
    "            position_b = -1\n",
    "        else:\n",
    "            position_b = position\n",
    "        # 比较数字\n",
    "        if b[position_b] > a[position_a]:\n",
    "            return False\n",
    "        elif b[position_b] < a[position_a]:\n",
    "            return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "def be_rich(input_arr):\n",
    "    \"\"\"主程序\"\"\"\n",
    "    for i in range(len(input_arr)):\n",
    "        input_arr[i] = str(input_arr[i])  # 把数值变成字符串\n",
    "    result = merge_sort_2(input_arr)      # 用归并排序获取有序列表 \n",
    "    print(\"最大数值为：\", \"\".join(result))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "最大数值为： 716351433331231\n",
      "最大数值为： 996211926333111\n",
      "最大数值为： 00000\n"
     ]
    }
   ],
   "source": [
    "be_rich([4,51,71,63,31,23,1,33,3])\n",
    "be_rich([9,92,6,96211,111,33,3])\n",
    "be_rich([0,0,0,0,0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "最大数值为0，欺骗人的！\n",
      "最大数值为： 10000\n"
     ]
    }
   ],
   "source": [
    "def be_rich_2(input_arr):\n",
    "    \"\"\"主程序\"\"\"\n",
    "    all_zero = not any(input_arr) # 增加判断特殊值判断\n",
    "    if all_zero:\n",
    "        print(\"最大数值为0，欺骗人的！\", )\n",
    "        return\n",
    "    for i in range(len(input_arr)):\n",
    "        input_arr[i] = str(input_arr[i])  # 把数值变成字符串\n",
    "    result = merge_sort_2(input_arr)      # 用归并排序获取有序列表 \n",
    "    print(\"最大数值为：\", \"\".join(result))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 快速排序"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def partition(arr, begin, end):\n",
    "    base_index = begin  # 选择序列第一个元素作为基准值\n",
    "    for i in range(begin+1, end+1):\n",
    "        if arr[i] <= arr[begin]: # 如果元素大于基准值位置不变，若否则调换位置\n",
    "            base_index += 1       # 记录基准值的新位置\n",
    "            arr[i], arr[base_index] = arr[base_index], arr[i]\n",
    "    arr[base_index], arr[begin] = arr[begin], arr[base_index] # 把基准值放到新位置\n",
    "    return base_index\n",
    "\n",
    "def quick_sort_recursion(arr, begin, end):\n",
    "    if begin >= end: # 若开始下标和结束下标重合，就是最小的子序列不用继续拆解\n",
    "        return\n",
    "    base_index = partition(arr, begin, end) # 找出基准值的新下标\n",
    "    quick_sort_recursion(arr, begin, base_index-1) # 小于基准值的子序列\n",
    "    quick_sort_recursion(arr, base_index+1, end) # 大于基准值的子序列\n",
    "\n",
    "def quick_sort(arr):\n",
    "    \"\"\"快速排序\"\"\"\n",
    "    begin = 0          # 刚开始是整个列表\n",
    "    end = len(arr) - 1 # 列表最末端下标\n",
    "    quick_sort_recursion(arr, begin, end) # 递归求解"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7]\n"
     ]
    }
   ],
   "source": [
    "arr = [4,5,7,6,3,2,1]\n",
    "quick_sort(arr)\n",
    "print(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint  # 使用randint产生随机整数\n",
    "def partition_random(arr, begin, end):\n",
    "    \"\"\"优化选择基准值的方式\"\"\"\n",
    "    base_index = randint(begin, end)  # 随机选择序列某个元素作为基准值\n",
    "    arr[begin], arr[base_index] =  arr[base_index], arr[begin] # 把基准值调到最前面\n",
    "    base_index = begin\n",
    "    for i in range(begin+1, end+1):\n",
    "        if arr[i] <= arr[begin]: # 如果元素大于基准值位置不变，若否则调换位置\n",
    "            base_index += 1       # 记录基准值的新位置\n",
    "            arr[i], arr[base_index] = arr[base_index], arr[i]\n",
    "    arr[base_index], arr[begin] = arr[begin], arr[base_index] # 把基准值放到新位置\n",
    "    return base_index\n",
    "\n",
    "def quick_sort_recursion(arr, begin, end):\n",
    "    if begin >= end: # 若开始下标和结束下标重合，就是最小的子序列不用继续拆解\n",
    "        return\n",
    "    base_index = partition_random(arr, begin, end) # 找出基准值的新下标\n",
    "    quick_sort_recursion(arr, begin, base_index-1) # 小于基准值的子序列\n",
    "    quick_sort_recursion(arr, base_index+1, end) # 大于基准值的子序列\n",
    "\n",
    "def quick_sort(arr):\n",
    "    \"\"\"快速排序\"\"\"\n",
    "    begin = 0          # 刚开始是整个列表\n",
    "    end = len(arr) - 1 # 列表最末端下标\n",
    "    quick_sort_recursion(arr, begin, end) # 递归求解"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7]\n"
     ]
    }
   ],
   "source": [
    "arr = [4,5,7,6,3,2,1]\n",
    "quick_sort(arr)\n",
    "print(arr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###  挑战：荷兰国旗问题"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "def color_sort(arr):\n",
    "    \"\"\"荷兰国旗问题\"\"\"\n",
    "    red, white, blue = 0,0, len(arr) - 1 # 初始化指针位置 \n",
    "    while white <= blue:     # 白色指针小于蓝色指针，移动白色指针\n",
    "        if arr[white] == 0:  # 遇到红色球\n",
    "            # 白色指针指向红色球，用红色指针交换并向前移动（+1）白色和红色指针\n",
    "            arr[red], arr[white] = arr[white], arr[red]\n",
    "            red += 1\n",
    "            white += 1\n",
    "        elif arr[white] == 1: # 遇到白色球\n",
    "            # 白色指针指向白色球，则元素已经在正确的位置，因此只需向前移动白色指针\n",
    "            white += 1\n",
    "        else:                # 遇到蓝色球\n",
    "            # 白色指针向蓝色球，用蓝色指针交换，也就是交换最新的未分类元素，蓝色指针向后移动\n",
    "            arr[blue], arr[white] = arr[white], arr[blue]\n",
    "            blue -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 0, 0, 1, 1, 1, 1, 2, 2]\n"
     ]
    }
   ],
   "source": [
    "input_data = [0,1,2,1,1,0,2,1,0]\n",
    "color_sort(input_data)\n",
    "print(input_data)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python内置排序\n",
    "\n",
    "### 列表中的函数sort()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "升序： [1, 2, 3, 4, 5, 6, 7]\n",
      "降序： [7, 6, 5, 4, 3, 2, 1]\n",
      "按元素绝对值升序： [0, 1, -2, -2, 3, 8, 10, -11]\n",
      "按元素字符长度升序 ['Tom', 'Jack', 'louis', 'Merry', 'Anthony']\n"
     ]
    }
   ],
   "source": [
    "# 列表中的函数sort\n",
    "arr = [4,5,7,6,3,2,1]\n",
    "arr.sort()\n",
    "print(\"升序：\", arr)\n",
    "arr.sort(reverse=True)  # 降序排列\n",
    "print(\"降序：\", arr)\n",
    "arr_2 = [3, -2, 1, 8, 0, -11, -2, 10]\n",
    "arr_2.sort(key=abs)  # 按绝对值排列\n",
    "print(\"按元素绝对值升序：\", arr_2)\n",
    "arr_3 = ['louis', 'Tom', 'Merry', 'Jack', 'Anthony']\n",
    "arr_3.sort(key=len)  # 按字符长度排序\n",
    "print(\"按元素字符长度升序\", arr_3) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### sorted()函数的使用"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "升序: [1, 2, 3, 4, 5, 6, 7]\n",
      "输入列表： [4, 5, 7, 6, 3, 2, 1]\n",
      "降序: [7, 6, 5, 4, 3, 2, 1]\n"
     ]
    }
   ],
   "source": [
    "# sorted()函数的使用\n",
    "arr = [4,5,7,6,3,2,1]\n",
    "print(\"升序:\", sorted(arr))  # 默认是升序\n",
    "print(\"输入列表：\", arr)  # 不改变原来列表\n",
    "arr_2 = sorted(arr, reverse=True)  # 降序\n",
    "print(\"降序:\", arr_2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "通过第二个关键值来排序: [('a', 1), ('b', 2), ('c', 3), ('d', 4)]\n",
      "按元素字符长度降序1： ['Anthony', 'louis', 'Merry', 'Jack', 'Tom']\n",
      "按元素字符长度降序2： ['Anthony', 'louis', 'Merry', 'Jack', 'Tom']\n",
      "按元素字符长度降序3： ['Anthony', 'louis', 'Merry', 'Jack', 'Tom']\n"
     ]
    }
   ],
   "source": [
    "arr_3 = [('b',2),('a',1),('c',3),('d',4)]\n",
    "arr_4 = sorted(arr_3, key=lambda x:x[1])  # 选择用某个关键值来排序\n",
    "print(\"通过第二个关键值来排序:\", arr_4)\n",
    "arr_5 = ['louis', 'Tom', 'Merry', 'Jack', 'Anthony']\n",
    "arr_6 = sorted(arr_5, key=lambda x: len(x), reverse=True)  # 按字符长度排序, 用lambda可以更清晰表达\n",
    "print(\"按元素字符长度降序1：\", arr_6)\n",
    "arr_7 = sorted(arr_5, key=len, reverse=True)  # 按字符长度排序，不同表达方式\n",
    "print(\"按元素字符长度降序2：\", arr_6)\n",
    "# 选择用某个关键值来排序，不同表达方式\n",
    "def value_len(value):\n",
    "    return len(value)\n",
    "arr_8 = sorted(arr_5, key=value_len, reverse=True)  \n",
    "print(\"按元素字符长度降序3：\", arr_8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "原字典： {'b': 2, 'a': 1, 'c': 3, 'd': 4}\n",
      "字典的值排序 [('a', 1), ('b', 2), ('c', 3), ('d', 4)]\n",
      "多关键值排序： [('A', 3, 2), ('X', 1, 6), ('X', 2, 5)]\n"
     ]
    }
   ],
   "source": [
    "# 字典排序\n",
    "dict_1 = {'b':2, 'a':1, 'c':3, 'd':4}\n",
    "dict_2 = sorted(dict_1.items(), key=lambda x: x[1])\n",
    "print(\"原字典：\",dict_1)\n",
    "print(\"字典的值排序\", dict_2)\n",
    "# 多个关键值排序\n",
    "class cmp_list:\n",
    "    def __init__(self, a, b, c):\n",
    "        self.a = a\n",
    "        self.b = b\n",
    "        self.c = c\n",
    "    def __repr__(self):\n",
    "        return repr((self.a, self.b, self.c))\n",
    "\n",
    "multi_cmps = [cmp_list('X', 1, 6), cmp_list('A', 3, 2), cmp_list('X', 2, 5)]\n",
    "# 首先根据a的位置来排序，然后根据b的位置来排序\n",
    "res = sorted(multi_cmps, key=lambda x:(x.a, x.b))\n",
    "print(\"多关键值排序：\", res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
